<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Smallest Integer Divisible by K</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-body vscode-light">
        <h1 id="smallest-integer-divisible-by-k">Smallest Integer Divisible by K</h1>
<h1 id="1-lc-1015-smallest-integer-divisible-by-k">1. LC 1015 Smallest Integer Divisible by K</h1>
<ul>
<li><a href="https://leetcode.com/problems/smallest-integer-divisible-by-k/">https://leetcode.com/problems/smallest-integer-divisible-by-k/</a></li>
</ul>
<p>Given a positive integer K, you need to find the length of the smallest positive integer N such that N is divisible by K, and N only contains the digit 1.</p>
<p>Return the length of N. If there is no such N, return -1.</p>
<p>Note: N may not fit in a 64-bit signed integer.</p>
<pre><code><code><div>Example 1:

Input: K = 1
Output: 1
Explanation: The smallest answer is N = 1, which has length 1.
Example 2:

Input: K = 2
Output: -1
Explanation: There is no such positive integer N divisible by 2.
Example 3:

Input: K = 3
Output: 3
Explanation: The smallest answer is N = 111, which has length 3.
</div></code></code></pre>
<p>本题是数学题。暴力解法就是挨个遍历</p>
<pre><code><code><div>1 % K == 0 ?
11 % K == 0 ?
111 % K == 0 ?
1111 % K == 0 ?
...
</div></code></code></pre>
<p>这样一直查下去， 直到出现两种情况</p>
<ol>
<li>某个 1111...11 % K == 0  返回长度</li>
<li>无限循环，永远不等于0， 返回-1， 无解</li>
</ol>
<p>那么怎么判断什么情况下没有解呢?   因为 X mod K 永远最多只有 K种余数。 所以我们只需要循环K次就行了，如果循环K次，还没有找到余数为0的可能，那就无解了。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">smallestRepunitDivByK</span>(<span class="hljs-params">self, K: int</span>) -&gt; int:</span>
        r = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> N <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, K + <span class="hljs-number">1</span>):
            r = (r * <span class="hljs-number">10</span> + <span class="hljs-number">1</span>)        <span class="hljs-comment"># brutal solution</span>
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> r % K: <span class="hljs-keyword">return</span> N
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<p>上面的代码提交后能通过，但是耗时比较长，主要是r 会迅速增大。 这里有个数学技巧。我们注意到</p>
<pre><code>111 mod K  ==  (11 * 10 + 1) mod K ==  ( (11 mod K) * 10 + 1 ) mod K
1111 mod K  ==  (111 * 10 + 1) mod K ==  ( (111 mod K) * 10 + 1 ) mod K
...
</code></pre>
<p>所以可以简化一下，类似于伽罗海域上面的运算</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">smallestRepunitDivByK</span>(<span class="hljs-params">self, K: int</span>) -&gt; int:</span>
        r = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> N <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, K + <span class="hljs-number">1</span>):
            r = (r * <span class="hljs-number">10</span> + <span class="hljs-number">1</span>) % K  <span class="hljs-comment"># optical solution</span>
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> r: <span class="hljs-keyword">return</span> N
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>

    </body>
    </html>